#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;
struct ListNode
{
    int data;
    ListNode *next;
};
class List
{
protected:
    ListNode *Data;
    ListNode *pTail;
    int listLength;
    bool insertAfter(int elem, ListNode *node);
    bool insertBefore(int elem, ListNode *node);
    ListNode *getElemByPos(int pos);
    bool delListNode(ListNode *node);

public:
    List() : listLength(0)
    {
        Data = new ListNode;
        Data->next = NULL;
        pTail = NULL;
    };
    int reverseList();
    bool insertAt(int elem, int pos);
    bool insertAtHead(int elem);
    bool insertAtTail(int elem);
    int traverse();
};
bool List::delListNode(ListNode *node)
{
    if (node == NULL)
        return false;
    if (node->next == NULL) //尾部节点
    {
        ListNode *p = getElemByPos(this->listLength);
        if (p == NULL)
            return false;
        p->next = NULL;
        this->listLength--;
        return true;
    }
    else
    {
        node->data = node->next->data;
        ListNode *p = node->next;
        node->next = p->next;
        this->listLength--;
        return true;
    }
}
int List::reverseList()
{
    ListNode *p = this->Data;
    int cnt = 0,elem = 0;
    if(p->next!=NULL)p=p->next;
    while (p != NULL && cnt < this->listLength)
    {
        elem = p->data;
        if (delListNode(p) == true)
            insertAtHead(elem);
        traverse();
        cnt++;
    }
    return cnt;
}
bool List::insertAtHead(int elem) { return insertAt(elem, 1); }
bool List::insertAtTail(int elem) { return insertAt(elem, this->listLength + 1); }
ListNode *List::getElemByPos(int pos)
{
    if (pos < 1)
        return NULL;
    ListNode *p = this->Data;
    int j = 0;
    while (p != NULL && j < pos - 1)
    {
        p = p->next;
        j++;
    }
    return p;
}
bool List::insertBefore(int elem, ListNode *node)
{
    ListNode *tmp = new ListNode;
    tmp->data = node->data;
    tmp->next = node->next;
    node->next = tmp;
    return true;
}
bool List::insertAfter(int elem, ListNode *node)
{
    if (node == NULL)
        return false;
    ListNode *tmp = new ListNode;
    tmp->data = elem;
    tmp->next = node->next;
    node->next = tmp;
    if (tmp->next == NULL)
        pTail = tmp;
    this->listLength++;
    return true;
}
bool List::insertAt(int elem, int pos)
{
    ListNode *p = getElemByPos(pos);
    if (p == NULL)
        return false;
    return insertAfter(elem, p);
}
int List::traverse()
{
    int i = 0;
    ListNode *p = this->Data;
    if (this->listLength > 0)
        printf("\n列表长度%d,头元素:%d,尾元素:%d @@@:", this->listLength, this->Data->next->data, this->pTail->data);
    while (p->next != NULL)
    {
        p = p->next;
        printf(" %d", p->data);
        ++i;
    }
    return i;
}
int main()
{
    List *L = new List;
    for (int i = 1; i <= 10; ++i)
    {
        L->insertAt(i, i);
    }
    if (L->traverse())
    {
        cout << "\nSuccess!\n下面开始翻转列表" << endl;
        L->reverseList();
        L->traverse();
    }
    else
    {
        cout << "Something seems wrong." << endl;
    }
    return 0;
}